package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/count-nodes-equal-to-average-of-subtree'>统计值等于子树平均值的节点数(Count Nodes Equal to Average of Subtree)</a>
 * <p>给你一棵二叉树的根节点 root ，找出并返回满足要求的节点数，要求节点的值等于其 子树 中值的 平均值 。</p>
 * <p>
 * 注意：
 *     <ul>
 *         <li>n 个元素的平均值可以由 n 个元素 求和 然后再除以 n ，并 向下舍入 到最近的整数。</li>
 *         <li>root 的 子树 由 root 和它的所有后代组成。</li>
 *     </ul>
 * </p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：root = [4,8,5,0,1,null,6]
 *                      4
 *                    /   \
 *                   8     5
 *                 /  \     \
 *                0    1     6
 *      输出：5
 *      解释：
 *          对值为 4 的节点：子树的平均值 (4 + 8 + 5 + 0 + 1 + 6) / 6 = 24 / 6 = 4 。
 *          对值为 5 的节点：子树的平均值 (5 + 6) / 2 = 11 / 2 = 5 。
 *          对值为 0 的节点：子树的平均值 0 / 1 = 0 。
 *          对值为 1 的节点：子树的平均值 1 / 1 = 1 。
 *          对值为 6 的节点：子树的平均值 6 / 1 = 6 。
 *
 *  示例 2：
 *      输入：root = [1]
 *      输出：1
 *      解释：对值为 1 的节点：子树的平均值 1 / 1 = 1。
 *
 *  示例 3：
 *      输入：root = [1,null,3,null,1,null,3]
 *                      1
 *                        \
 *                         3
 *                           \
 *                             1
 *                               \
 *                                 3
 *      输出：1
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点数目在范围 [1, 1000] 内</li>
 *     <li>0 <= Node.val <= 1000</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/5/20 14:35
 */
public class LC2265CountNodesEqualToAverageOfSubtree_M {

    static class Solution {

        int ans = 0;

        public int averageOfSubtree(TreeNode root) {
            dfs(root);
            return ans;
        }

        /**
         * int[0]：以当前树为根节点的树，节点值之和
         * int[1]：以当前树为根节点的树，节点数量
         */
        private int[] dfs(TreeNode curr) {
            if (curr == null) {
                return new int[]{0, 0};
            }
            int[] left = dfs(curr.left);
            int[] right = dfs(curr.right);
            int sum = left[0] + right[0] + curr.val;
            int num = left[1] + right[1] + 1;
            int avg = sum / num;
            if (curr.val == avg) {
                ans++;
            }
            return new int[]{sum, num};
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution().averageOfSubtree(Generator.buildTree(4, 8, 5, 0, 1, null, 6)));
        System.out.println(new Solution().averageOfSubtree(Generator.buildTree(1)));
        System.out.println(new Solution().averageOfSubtree(Generator.buildTree(1, null, 3, null, 1, null, 3)));
    }
}
